import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class CountSmaller {

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> temp = new Stack<>();
        ans.add(0);
        stack.push(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > stack.peek()) {
                ans.add(stack.size());
                stack.push(nums[i]);
            } else {
                while (!stack.isEmpty() && stack.peek() < nums[i]) {
                    temp.push(stack.pop());
                }
                ans.add(stack.size());
                stack.push(nums[i]);
                while (!temp.isEmpty()) {
                    stack.push(temp.pop());
                }
            }
        }
        Collections.reverse(ans);
        return ans;
    }
}
